<!DOCTYPE html>
<html lang="zh">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 5.3.0">


  <link rel="apple-touch-icon" sizes="180x180" href="/yuwanzi.io/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/yuwanzi.io/images/favicon-32x32-next.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/yuwanzi.io/images/favicon-16x16-next.png">
  <link rel="mask-icon" href="/yuwanzi.io/images/logo.svg" color="#222">

<link rel="stylesheet" href="/yuwanzi.io/css/main.css">



<link rel="stylesheet" href="//cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free@5.15.1/css/all.min.css">
  <link rel="stylesheet" href="//cdn.jsdelivr.net/npm/animate.css@3.1.1/animate.min.css">

<script class="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"suyuhuan.gitee.io","root":"/yuwanzi.io/","images":"/yuwanzi.io/images","scheme":"Muse","version":"8.2.0","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12},"copycode":false,"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"fadeInDown","post_body":"fadeInDown","coll_header":"fadeInLeft","sidebar":"fadeInUp"}},"prism":false,"i18n":{"placeholder":"Suche...","empty":"We didn't find any results for the search: ${query}","hits_time":"${hits} results found in ${time} ms","hits":"${hits} results found"}};
  </script>
<meta name="description" content="在数学中,一个图(Graph)是表示物件与物件之间关系的方法,是图论的基本研究对象.一个图是由顶点(Vertex)与连接这些顶点的边(Edge)组成的. 图论作为数学领域中的一个重要分支已经有数百年的历史了.人们发现了图的许多重要而实用的性质,发明了许多重要的算法,给你一个图(Graph)你可以联想到许多问题: 两个顶点之间是否存在一条链接?如果存在,两个顶点之间最短的连接又是哪一条?…. 在生活">
<meta property="og:type" content="article">
<meta property="og:title" content="图的那点事儿(1)-无向图">
<meta property="og:url" content="https://suyuhuan.gitee.io/yuwanzi.io/2017/07/18/2017-07-18-Graph_UndirectedGraph/index.html">
<meta property="og:site_name" content="玉丸子 | Blog">
<meta property="og:description" content="在数学中,一个图(Graph)是表示物件与物件之间关系的方法,是图论的基本研究对象.一个图是由顶点(Vertex)与连接这些顶点的边(Edge)组成的. 图论作为数学领域中的一个重要分支已经有数百年的历史了.人们发现了图的许多重要而实用的性质,发明了许多重要的算法,给你一个图(Graph)你可以联想到许多问题: 两个顶点之间是否存在一条链接?如果存在,两个顶点之间最短的连接又是哪一条?…. 在生活">
<meta property="og:locale">
<meta property="og:image" content="http://algs4.cs.princeton.edu/41graph/images/graph-anatomy.png">
<meta property="og:image" content="http://algs4.cs.princeton.edu/41graph/images/tree.png">
<meta property="og:image" content="http://algs4.cs.princeton.edu/41graph/images/forest.png">
<meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/e/e8/Simple-bipartite-graph.svg/600px-Simple-bipartite-graph.svg.png">
<meta property="og:image" content="http://algs4.cs.princeton.edu/41graph/images/adjacency-lists.png">
<meta property="og:image" content="http://algs4.cs.princeton.edu/41graph/images/search-api.png">
<meta property="og:image" content="http://algs4.cs.princeton.edu/41graph/images/paths-api.png">
<meta property="og:image" content="http://algs4.cs.princeton.edu/41graph/images/cc-api.png">
<meta property="og:image" content="http://algs4.cs.princeton.edu/41graph/images/routes.png">
<meta property="og:image" content="http://algs4.cs.princeton.edu/41graph/images/symbol-graph-api.png">
<meta property="og:image" content="http://algs4.cs.princeton.edu/41graph/images/symbol-graph.png">
<meta property="article:published_time" content="2017-07-18T03:00:00.000Z">
<meta property="article:modified_time" content="2020-11-07T00:58:17.000Z">
<meta property="article:author" content="玉丸子">
<meta property="article:tag" content="2017">
<meta property="article:tag" content="Algorithms">
<meta property="article:tag" content="Graph">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="http://algs4.cs.princeton.edu/41graph/images/graph-anatomy.png">


<link rel="canonical" href="https://suyuhuan.gitee.io/yuwanzi.io/2017/07/18/2017-07-18-Graph_UndirectedGraph/">


<script class="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : false,
    isPost : true,
    lang   : 'zh'
  };
</script>
<title>图的那点事儿(1)-无向图 | 玉丸子 | Blog</title>
  




  <noscript>
  <style>
  body { margin-top: 2rem; }

  .use-motion .menu-item,
  .use-motion .sidebar,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header {
    visibility: visible;
  }

  .use-motion .header,
  .use-motion .site-brand-container .toggle,
  .use-motion .footer { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle,
  .use-motion .custom-logo-image {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line {
    transform: scaleX(1);
  }

  .search-pop-overlay, .sidebar-nav { display: none; }
  .sidebar-panel { display: block; }
  </style>
</noscript>

<link rel="alternate" href="/yuwanzi.io/atom.xml" title="玉丸子 | Blog" type="application/atom+xml">
</head>

<body itemscope itemtype="http://schema.org/WebPage" class="use-motion">
  <div class="headband"></div>

  <main class="main">
    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="Navigationsleiste an/ausschalten" role="button">
    </div>
  </div>

  <div class="site-meta">

    <a href="/yuwanzi.io/" class="brand" rel="start">
      <i class="logo-line"></i>
      <h1 class="site-title">玉丸子 | Blog</h1>
      <i class="logo-line"></i>
    </a>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
    </div>
  </div>
</div>







</div>
        
  
  <div class="toggle sidebar-toggle" role="button">
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
  </div>

  <aside class="sidebar">

    <div class="sidebar-inner sidebar-nav-active sidebar-toc-active">
      <ul class="sidebar-nav">
        <li class="sidebar-nav-toc">
          Inhaltsverzeichnis
        </li>
        <li class="sidebar-nav-overview">
          Übersicht
        </li>
      </ul>

      <div class="sidebar-panel-container">
        <!--noindex-->
        <div class="post-toc-wrap sidebar-panel">
            <div class="post-toc animated"><ol class="nav"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%9F%BA%E6%9C%AC%E6%9C%AF%E8%AF%AD"><span class="nav-number">1.</span> <span class="nav-text">基本术语</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%A0%91"><span class="nav-number">2.</span> <span class="nav-text">树</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E4%BA%8C%E5%88%86%E5%9B%BE"><span class="nav-number">3.</span> <span class="nav-text">二分图</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%97%A0%E5%90%91%E5%9B%BE"><span class="nav-number">4.</span> <span class="nav-text">无向图</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E5%9B%BE%E7%9A%84%E8%A1%A8%E7%A4%BA%E6%96%B9%E6%B3%95"><span class="nav-number">4.1.</span> <span class="nav-text">图的表示方法</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E5%AE%9E%E7%8E%B0"><span class="nav-number">4.2.</span> <span class="nav-text">实现</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2"><span class="nav-number">5.</span> <span class="nav-text">深度优先搜索</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E9%80%92%E5%BD%92%E5%AE%9E%E7%8E%B0"><span class="nav-number">5.1.</span> <span class="nav-text">递归实现</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E9%9D%9E%E9%80%92%E5%BD%92%E5%AE%9E%E7%8E%B0"><span class="nav-number">5.2.</span> <span class="nav-text">非递归实现</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%AF%BB%E6%89%BE%E8%B7%AF%E5%BE%84"><span class="nav-number">6.</span> <span class="nav-text">寻找路径</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2"><span class="nav-number">7.</span> <span class="nav-text">广度优先搜索</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BF%9E%E9%80%9A%E5%88%86%E9%87%8F"><span class="nav-number">8.</span> <span class="nav-text">连通分量</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%A3%80%E6%B5%8B%E7%8E%AF%E4%B8%8E%E5%8F%8C%E8%89%B2%E9%97%AE%E9%A2%98"><span class="nav-number">9.</span> <span class="nav-text">检测环与双色问题</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E6%A3%80%E6%B5%8B%E7%8E%AF"><span class="nav-number">9.1.</span> <span class="nav-text">检测环</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E6%A3%80%E6%B5%8B%E5%8F%8C%E8%89%B2"><span class="nav-number">9.2.</span> <span class="nav-text">检测双色</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E7%AC%A6%E5%8F%B7%E5%9B%BE"><span class="nav-number">10.</span> <span class="nav-text">符号图</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="nav-number">10.1.</span> <span class="nav-text">代码实现</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%8F%82%E8%80%83%E8%B5%84%E6%96%99"><span class="nav-number">11.</span> <span class="nav-text">参考资料</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%9B%BE%E7%9A%84%E9%82%A3%E7%82%B9%E4%BA%8B%E5%84%BF"><span class="nav-number">12.</span> <span class="nav-text">图的那点事儿</span></a></li></ol></div>
        </div>
        <!--/noindex-->

        <div class="site-overview-wrap sidebar-panel">
          <div class="site-author site-overview-item animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
  <p class="site-author-name" itemprop="name">玉丸子</p>
  <div class="site-description" itemprop="description">这里是玉丸子的个人博客,与你一起发现更大的世界。</div>
</div>
<div class="site-state-wrap site-overview-item animated">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/yuwanzi.io/archives">
          <span class="site-state-item-count">68</span>
          <span class="site-state-item-name">Artikel</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
            <a href="/yuwanzi.io/categories/">
        <span class="site-state-item-count">39</span>
        <span class="site-state-item-name">Kategorien</span></a>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/yuwanzi.io/tags/">
        <span class="site-state-item-count">46</span>
        <span class="site-state-item-name">schlagwörter</span></a>
      </div>
  </nav>
</div>



        </div>
      </div>
    </div>
  </aside>
  <div class="sidebar-dimmer"></div>


    </header>

    
  <div class="back-to-top" role="button">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>

<noscript>
  <div class="noscript-warning">Theme NexT works best with JavaScript enabled</div>
</noscript>


    <div class="main-inner post posts-expand">


  


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="zh">
    <link itemprop="mainEntityOfPage" href="https://suyuhuan.gitee.io/yuwanzi.io/2017/07/18/2017-07-18-Graph_UndirectedGraph/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/yuwanzi.io/images/avatar.gif">
      <meta itemprop="name" content="玉丸子">
      <meta itemprop="description" content="这里是玉丸子的个人博客,与你一起发现更大的世界。">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="玉丸子 | Blog">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          图的那点事儿(1)-无向图
        </h1>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">Veröffentlicht am</span>

      <time title="Erstellt: 2017-07-18 11:00:00" itemprop="dateCreated datePublished" datetime="2017-07-18T11:00:00+08:00">2017-07-18</time>
    </span>
      <span class="post-meta-item">
        <span class="post-meta-item-icon">
          <i class="far fa-calendar-check"></i>
        </span>
        <span class="post-meta-item-text">Bearbeitet am</span>
        <time title="Geändert am: 2020-11-07 08:58:17" itemprop="dateModified" datetime="2020-11-07T08:58:17+08:00">2020-11-07</time>
      </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">in</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/yuwanzi.io/categories/Algorithms/" itemprop="url" rel="index"><span itemprop="name">Algorithms</span></a>
        </span>
          . 
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/yuwanzi.io/categories/Algorithms/Graph/" itemprop="url" rel="index"><span itemprop="name">Graph</span></a>
        </span>
    </span>

  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
        <p>在数学中,一个<code>图(Graph)</code>是表示物件与物件之间关系的方法,是<code>图论</code>的基本研究对象.一个图是由<code>顶点(Vertex)</code>与连接这些<code>顶点</code>的<code>边(Edge)</code>组成的.</p>
<p><code>图论</code>作为数学领域中的一个重要分支已经有数百年的历史了.人们发现了图的许多重要而实用的性质,发明了许多重要的算法,给你一个<code>图(Graph)</code>你可以联想到许多问题: 两个<code>顶点</code>之间是否存在一条链接?如果存在,两个<code>顶点</code>之间最短的连接又是哪一条?….</p>
<p>在生活中,到处都可以发现<code>图论</code>的应用: </p>
<ul>
<li>地图: 在使用地图中,我们经常会想知道”从xx到xx的最短路线”这样的问题,要回答这些问题,就需要把地图抽象成一个<code>图(Graph)</code>,十字路口就是<code>顶点</code>,公路就是<code>边</code>.</li>
</ul>
<ul>
<li>互联网: 整个互联网其实就是一张<code>图</code>,它的<code>顶点</code>为网页,<code>边</code>为超链接.而<code>图论</code>可以帮助我们在网络上定位信息.</li>
</ul>
<ul>
<li>任务调度: 当一些任务拥有优先级限制且需要满足前置条件时,如何在满足条件的情况下用最少的时间完成就需要用到<code>图论</code>.</li>
</ul>
<ul>
<li>社交网络: 在使用社交网站时,你就是一个<code>顶点</code>,你和你的朋友建立的关系则是<code>边</code>.分析这些社交网络的性质也是<code>图论</code>的一个重要应用.</li>
</ul>
<p><strong><code>图</code>就是由一组<code>顶点</code>和一组能够将两个<code>顶点</code>相连的<code>边</code>组成的.</strong></p>
<h3 id="基本术语"><a href="#基本术语" class="headerlink" title="基本术语"></a>基本术语</h3><hr>
<p><img src="http://algs4.cs.princeton.edu/41graph/images/graph-anatomy.png" alt="图中的元素"></p>
<ul>
<li>相邻: 当两个<code>顶点</code>通过一条<code>边</code>相连接时,这两个<code>顶点</code>即为相邻的(也可以说这条<code>边</code>依附于这两个<code>顶点</code>).</li>
</ul>
<ul>
<li>度数: 某个<code>顶点</code>的<code>度数</code>即为依附于它的<code>边</code>的总数.</li>
</ul>
<ul>
<li>阶: <code>图G</code>中的<code>顶点集合V</code>的大小称为<code>G</code>的阶.</li>
</ul>
<ul>
<li>自环: 一条连接一个<code>顶点</code>和其自身的<code>边</code>.</li>
</ul>
<ul>
<li><p>平行边: 连接同一对<code>顶点</code>的两条<code>边</code>称为平行边.</p>
</li>
<li><p>桥: 如果去掉一条<code>边</code>会使整个<code>图</code>变成<code>非连通图</code>,则该<code>边</code>称为桥.</p>
</li>
<li><p>路径: 当<code>顶点v</code>到<code>顶点w</code>是连通时,我们用<code>v-&gt;x-&gt;y-&gt;w</code>为一条<code>v</code>到<code>w</code>的路径,用<code>v-&gt;x-&gt;y-&gt;v</code>表示一条环.</p>
</li>
</ul>
<ul>
<li>子图: 也称作<code>连通分量</code>,它由一张<code>图</code>的所有边的一个子集组成的<code>图</code>(以及依附的所有顶点).</li>
</ul>
<ul>
<li>连通图: <code>连通图</code>是一个整体,而<code>非连通图</code>则包含两个或多个<code>连通分量</code>.</li>
</ul>
<ul>
<li>稀疏图: 如果一张图中不同的<code>边</code>的数量在<code>顶点</code>总数<code>V</code>的一个小的常数倍内,那么该图就为稀疏图,否则为稠密图.</li>
</ul>
<ul>
<li>简单图与多重图: 含有<code>平行边</code>与<code>自环</code>的图称为<code>多重图</code>,而不含有<code>平行边</code>和<code>自环</code>的图称为<code>简单图</code>.</li>
</ul>
<h3 id="树"><a href="#树" class="headerlink" title="树"></a>树</h3><hr>
<p><img src="http://algs4.cs.princeton.edu/41graph/images/tree.png" alt="树"></p>
<p><img src="http://algs4.cs.princeton.edu/41graph/images/forest.png" alt="森林"></p>
<p>树是一张<code>无环连通图</code>,互不相连的树组成的集合称为森林.<code>连通图</code>的<code>生成树</code>是它的一张子图,它含有图中的所有顶点且是一棵树.图的<code>生成树森林</code>是它的所有<code>连通分量</code>的<code>生成树</code>的集合.</p>
<p>图<code>G</code>只要满足以下性质,那么它就是一棵树: </p>
<ul>
<li><code>G</code>有<code>V-1</code>条边且不含有环.</li>
</ul>
<ul>
<li><code>G</code>有<code>V-1</code>条边且是连通的.</li>
</ul>
<ul>
<li><code>G</code>是连通的,但删除任意一条边都会使它不再连通.</li>
</ul>
<ul>
<li><code>G</code>是无环图,但添加任意一条边都会产生一条环.</li>
</ul>
<ul>
<li><code>G</code>中的任意一对顶点之间仅存在一条简单路径(一条没有重复顶点的路径).</li>
</ul>
<h3 id="二分图"><a href="#二分图" class="headerlink" title="二分图"></a>二分图</h3><hr>
<p><img src="https://upload.wikimedia.org/wikipedia/commons/thumb/e/e8/Simple-bipartite-graph.svg/600px-Simple-bipartite-graph.svg.png" alt="U和V就是两个顶点集合"></p>
<p><code>二分图</code>是一种能够将所有<code>顶点</code>分为两部分的图,其中<code>图</code>的每条边所连接的两个<code>顶点</code>都分别属于不同的部分.</p>
<p>设<code>G = (V,E)</code>为一张<code>无向图</code>,如果顶点<code>V</code>可以分割为两个互不相交的子集<code>(U,V)</code>,且图中的每条边<code>(x,y)</code>所关联的两个顶点<code>x</code>,<code>y</code>分别属于这两个不同的顶点集合<code>(x in U , y in V)</code>,则<code>G</code>为<code>二分图</code>.</p>
<p>也可以将<code>(U,V)</code>当做一张<code>着色图</code>: <code>U</code>中的所有顶点为蓝色,<code>V</code>中的所有顶点为绿色,每条边所关联的两个<code>顶点</code>颜色不同.</p>
<h3 id="无向图"><a href="#无向图" class="headerlink" title="无向图"></a>无向图</h3><hr>
<p><code>无向图</code>是一种最简单的图模型,它的每条边都没有方向.</p>
<h4 id="图的表示方法"><a href="#图的表示方法" class="headerlink" title="图的表示方法"></a>图的表示方法</h4><hr>
<p>实现一张<code>图</code>的<code>API</code>需要满足以下两个要求:</p>
<ol>
<li>必须为可能在应用中碰到的各种类型的<code>图</code>预留出足够的空间.</li>
</ol>
<ol start="2">
<li><code>图</code>的实现一定要足够快(因为这是所有处理<code>图</code>的算法的基础结构).</li>
</ol>
<p>有以下三种数据结构能够用来表示一张图:</p>
<ul>
<li>邻接矩阵: 使用一个<code>V * V</code>的布尔矩阵.当顶点<code>v</code>和顶点<code>w</code>之间有相连接的<code>边</code>时,将<code>v</code>行<code>w</code>列的元素设为<code>true</code>,否则为<code>false</code>.这种方法不符合第一个条件,当<code>图</code>的顶点非常多时,邻接矩阵所需的空间将会非常大.且它无法表示平行边.</li>
</ul>
<ul>
<li>边的数组: 使用一个<code>Edge</code>类,它含有两个<code>int</code>成员变量来表示所依附的顶点.这种方法简单直接但不满足第二个条件(要实现查询邻接点的函数需要检查图中的所有边).</li>
</ul>
<ul>
<li>邻接表数组: <strong>使用一个<code>顶点</code>为索引的<code>链表数组</code>,其中的每个元素都是和该<code>顶点</code>相邻的顶点列表(邻接点)</strong>.这种方法同时满足了两个条件,我们会使用这种方法来实现<code>图</code>的数据结构.</li>
</ul>
<p><img src="http://algs4.cs.princeton.edu/41graph/images/adjacency-lists.png" alt="邻接表数组"></p>
<h4 id="实现"><a href="#实现" class="headerlink" title="实现"></a>实现</h4><hr>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">interface</span> <span class="title">Graph</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">vertex</span><span class="params">()</span></span>;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">edge</span><span class="params">()</span></span>;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">addEdge</span><span class="params">(<span class="keyword">int</span> v, <span class="keyword">int</span> w)</span></span>;</span><br><span class="line"></span><br><span class="line">    <span class="function">Iterable&lt;Integer&gt; <span class="title">adj</span><span class="params">(<span class="keyword">int</span> v)</span></span>;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">degree</span><span class="params">(<span class="keyword">int</span> v)</span></span>;</span><br><span class="line"></span><br><span class="line">    <span class="function">String <span class="title">toString</span><span class="params">()</span></span>;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">UndirectedGraph</span> <span class="keyword">implements</span> <span class="title">Graph</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">final</span> String NEW_LINE_SEPARATOR = System.getProperty(<span class="string">&quot;line.separator&quot;</span>);</span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">final</span> <span class="keyword">int</span> vertex; <span class="comment">// 顶点</span></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span> edge; <span class="comment">// 边</span></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">final</span> Bag&lt;Integer&gt;[] adjacent; <span class="comment">// 邻接表数组,Bag是一个没有实现删除操作的Stack</span></span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">UndirectedGraph</span><span class="params">(<span class="keyword">int</span> vertex)</span> </span>&#123;</span><br><span class="line">        checkVertex(vertex);</span><br><span class="line"></span><br><span class="line">        <span class="keyword">this</span>.vertex = vertex;</span><br><span class="line">        <span class="keyword">this</span>.edge = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">this</span>.adjacent = (Bag&lt;Integer&gt;[]) <span class="keyword">new</span> Bag[vertex];</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> v = <span class="number">0</span>; v &lt; vertex; v++)</span><br><span class="line">            adjacent[v] = <span class="keyword">new</span> Bag&lt;Integer&gt;();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 读取一个文件并初始化为无向图</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">UndirectedGraph</span><span class="params">(Scanner scanner)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (scanner == <span class="keyword">null</span>)</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;Specified input stream must not null!&quot;</span>);</span><br><span class="line"></span><br><span class="line">        <span class="keyword">try</span> &#123;</span><br><span class="line">			<span class="comment">// 文件的第一行为顶点数</span></span><br><span class="line">            <span class="keyword">this</span>.vertex = scanner.nextInt();</span><br><span class="line">            checkVertex(<span class="keyword">this</span>.vertex);</span><br><span class="line">			<span class="comment">// 文件的第二行为边数</span></span><br><span class="line">            <span class="keyword">int</span> edge = scanner.nextInt();</span><br><span class="line">            checkEdge(<span class="keyword">this</span>.edge);</span><br><span class="line">            <span class="keyword">this</span>.adjacent = (Bag&lt;Integer&gt;[]) <span class="keyword">new</span> Bag[<span class="keyword">this</span>.vertex];</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> v = <span class="number">0</span>; v &lt; <span class="keyword">this</span>.vertex; v++)</span><br><span class="line">                adjacent[v] = <span class="keyword">new</span> Bag&lt;Integer&gt;();</span><br><span class="line">			</span><br><span class="line">			<span class="comment">// 文件的剩余行为相连的顶点对 </span></span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; edge; i++) &#123;</span><br><span class="line">                <span class="keyword">int</span> v = scanner.nextInt();</span><br><span class="line">                <span class="keyword">int</span> w = scanner.nextInt();</span><br><span class="line">                addEdge(v, w);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125; <span class="keyword">catch</span> (NoSuchElementException e) &#123;</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;Invalid input format in Undirected Graph constructor&quot;</span>, e);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">UndirectedGraph</span><span class="params">(Graph graph)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">this</span>(graph.vertex());</span><br><span class="line">        <span class="keyword">this</span>.edge = graph.edge();</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> v = <span class="number">0</span>; v &lt; <span class="keyword">this</span>.vertex; v++) &#123;</span><br><span class="line">            <span class="comment">// reverse so that adjacency list is in same order as original</span></span><br><span class="line">            Stack&lt;Integer&gt; stack = <span class="keyword">new</span> Stack&lt;Integer&gt;();</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> w : graph.adj(v))</span><br><span class="line">                stack.push(w);</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> w : stack)</span><br><span class="line">                adjacent[v].add(w);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">checkVertex</span><span class="params">(<span class="keyword">int</span> vertex)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (vertex &lt;= <span class="number">0</span>)</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;Number of vertices must be positive number!&quot;</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">checkEdge</span><span class="params">(<span class="keyword">int</span> edge)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (edge &lt; <span class="number">0</span>)</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;Number of edges must be positive number!&quot;</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">vertex</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> vertex;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">edge</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> edge;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 添加一条连接v和w的边,由于是无向图所以这条边会出现两次</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">addEdge</span><span class="params">(<span class="keyword">int</span> v, <span class="keyword">int</span> w)</span> </span>&#123;</span><br><span class="line">        validateVertex(v);</span><br><span class="line">        validateVertex(w);</span><br><span class="line">        adjacent[v].add(w);</span><br><span class="line">        adjacent[w].add(v);</span><br><span class="line">        edge++;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> Iterable&lt;Integer&gt; <span class="title">adj</span><span class="params">(<span class="keyword">int</span> v)</span> </span>&#123;</span><br><span class="line">        validateVertex(v);</span><br><span class="line">        <span class="keyword">return</span> adjacent[v];</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">degree</span><span class="params">(<span class="keyword">int</span> v)</span> </span>&#123;</span><br><span class="line">        validateVertex(v);</span><br><span class="line">        <span class="keyword">return</span> adjacent[v].size();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">validateVertex</span><span class="params">(<span class="keyword">int</span> vertex)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (vertex &lt; <span class="number">0</span> || vertex &gt;= <span class="keyword">this</span>.vertex)</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;Vertex &quot;</span> + vertex + <span class="string">&quot; is not between 0 and &quot;</span> + (<span class="keyword">this</span>.vertex - <span class="number">1</span>));</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> String <span class="title">toString</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        StringBuilder sb = <span class="keyword">new</span> StringBuilder();</span><br><span class="line">        sb.append(<span class="string">&quot;Vertices: &quot;</span>).append(vertex).append(<span class="string">&quot; Edges: &quot;</span>).append(edge).append(NEW_LINE_SEPARATOR);</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> v = <span class="number">0</span>; v &lt; vertex; v++) &#123;</span><br><span class="line">            sb.append(v).append(<span class="string">&quot;: &quot;</span>);</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> w : adjacent[v])</span><br><span class="line">                sb.append(w).append(<span class="string">&quot; &quot;</span>);</span><br><span class="line">            sb.append(NEW_LINE_SEPARATOR);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> sb.toString();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">main</span><span class="params">(String[] args)</span> <span class="keyword">throws</span> FileNotFoundException </span>&#123;</span><br><span class="line">        InputStream inputStream =</span><br><span class="line">                UndirectedGraph.class.getResourceAsStream(<span class="string">&quot;/graph_file/C4_1_UndirectedGraphs/&quot;</span> + args[<span class="number">0</span>]);</span><br><span class="line">        Scanner scanner = <span class="keyword">new</span> Scanner(inputStream, <span class="string">&quot;UTF-8&quot;</span>);</span><br><span class="line">        Graph graph = <span class="keyword">new</span> UndirectedGraph(scanner);</span><br><span class="line">        System.out.println(graph);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>上面的这个实现拥有以下特点: </p>
<ul>
<li>使用的空间和<code>V + E</code>成正比.</li>
</ul>
<ul>
<li>添加一条边所需的时间为常数.</li>
</ul>
<ul>
<li>遍历顶点<code>v</code>的所有邻接点所需的时间和<code>v</code>的度数成正比(处理每个邻接点所需的时间为常数).</li>
</ul>
<ul>
<li>边的插入顺序决定了邻接表中顶点的出现顺序.</li>
</ul>
<ul>
<li>支持平行边与自环.</li>
</ul>
<ul>
<li>不支持添加或删除顶点的操作(如果想要支持这些操作需要使用一个<code>符号表</code>来代替由顶点索引构成的数组).</li>
</ul>
<ul>
<li>不支持删除边的操作(如果想要支持这个操作需要使用一个<code>SET</code>来代替<code>Bag</code>来实现邻接表,这种方法也叫<code>邻接集</code>).</li>
</ul>
<p>每种<code>图</code>实现的性能复杂度如下表: </p>
<table>
<thead>
<tr>
<th>数据结构</th>
<th>所需空间</th>
<th>添加一条边v - w</th>
<th>检查w和v是否相邻</th>
<th>遍历v的所有邻接点</th>
</tr>
</thead>
<tbody><tr>
<td>边的数组</td>
<td>E</td>
<td>1</td>
<td>E</td>
<td>E</td>
</tr>
<tr>
<td>邻接矩阵</td>
<td>V^2</td>
<td>1</td>
<td>1</td>
<td>V</td>
</tr>
<tr>
<td>邻接表</td>
<td>E+V</td>
<td>1</td>
<td>degree(V)</td>
<td>degree(V)</td>
</tr>
<tr>
<td>邻接集</td>
<td>E+V</td>
<td>logV</td>
<td>logV</td>
<td>logV+degree(V)</td>
</tr>
</tbody></table>
<blockquote>
<p>本文中的所有完整代码可以到我的<a target="_blank" rel="noopener" href="https://github.com/SylvanasSun/algs4-study/tree/master/src/main/java/chapter4_graphs/C4_1_UndirectedGraphs">GitHub</a>中查看.</p>
</blockquote>
<h3 id="深度优先搜索"><a href="#深度优先搜索" class="headerlink" title="深度优先搜索"></a>深度优先搜索</h3><hr>
<p>处理<code>图</code>的基本问题: <code>v 到 w是否是相连的?</code>. <code>深度优先搜索</code>就是用于解决这样问题的,它会<strong>沿着<code>图</code>的<code>边</code>寻找和<code>起点</code>连通的所有<code>顶点</code>.</strong></p>
<p><img src="http://algs4.cs.princeton.edu/41graph/images/search-api.png" alt="搜索的基本API"></p>
<p>如其名一样,<code>深度优先搜素</code>就是沿着<code>图</code>的<code>深度</code>来遍历<code>顶点</code>,它类似于走迷宫,会沿着一条路径一直走,直到走到尽头时再回退到上一个路口.为了防止迷路,还需要使用工具来标记已走过的路口(在我们的代码实现中使用一个布尔数组来进行标记).</p>
<h4 id="递归实现"><a href="#递归实现" class="headerlink" title="递归实现"></a>递归实现</h4><hr>
<p>使用递归方法来实现<code>深度优先搜索</code>会很简洁,当遇到一个<code>顶点</code>时:</p>
<ul>
<li>将它标记为已访问.</li>
</ul>
<ul>
<li>递归地访问它的所有没有被访问过的邻接点.</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">DepthFirstSearch</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">final</span> <span class="keyword">boolean</span>[] marked; <span class="comment">// 标记已访问过的顶点</span></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span> count;  <span class="comment">// 记录起点连通的顶点数</span></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">final</span> Graph graph;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">DepthFirstSearch</span><span class="params">(Graph graph, <span class="keyword">int</span> originPoint)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">this</span>.graph = graph;</span><br><span class="line">        <span class="keyword">this</span>.count = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">this</span>.marked = <span class="keyword">new</span> <span class="keyword">boolean</span>[graph.vertex()];</span><br><span class="line">        validateVertex(originPoint);</span><br><span class="line">		<span class="comment">// 从起点开始进行深度优先搜索</span></span><br><span class="line">        depthSearch(originPoint);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">count</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> count;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">marked</span><span class="params">(<span class="keyword">int</span> vertex)</span> </span>&#123;</span><br><span class="line">        validateVertex(vertex);</span><br><span class="line">        <span class="keyword">return</span> marked[vertex];</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">depthSearch</span><span class="params">(<span class="keyword">int</span> vertex)</span> </span>&#123;</span><br><span class="line">        marked[vertex] = <span class="keyword">true</span>;</span><br><span class="line">        count++;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> adj : graph.adj(vertex)) &#123;</span><br><span class="line">			<span class="comment">// 遍历邻接点,如果未访问则递归调用</span></span><br><span class="line">            <span class="keyword">if</span> (!marked[adj])</span><br><span class="line">                depthSearch(adj);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">validateVertex</span><span class="params">(<span class="keyword">int</span> vertex)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> length = marked.length;</span><br><span class="line">        <span class="keyword">if</span> (vertex &lt; <span class="number">0</span> || vertex &gt;= length)</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;Vertex &quot;</span> + vertex + <span class="string">&quot; is not between 0 and &quot;</span> + (length - <span class="number">1</span>));</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h4 id="非递归实现"><a href="#非递归实现" class="headerlink" title="非递归实现"></a>非递归实现</h4><hr>
<p>如果是了解<code>JVM</code>中函数调用的小伙伴们应该知道,函数都会封装成一个个<code>栈帧</code>然后压入<code>虚拟机栈</code>,上述的递归实现其实就是在隐式的使用到了<code>栈</code>,要想实现非递归,我们需要显式使用<code>栈</code>这个数据结构.</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">NonrecursiveDFS</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">final</span> <span class="keyword">boolean</span>[] marked; </span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">final</span> Iterator&lt;Integer&gt;[] adj;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">NonrecursiveDFS</span><span class="params">(Graph graph, <span class="keyword">int</span> originPoint)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> vertex = graph.vertex();</span><br><span class="line">        <span class="keyword">this</span>.marked = <span class="keyword">new</span> <span class="keyword">boolean</span>[vertex];</span><br><span class="line"></span><br><span class="line">        validateVertex(originPoint);</span><br><span class="line"></span><br><span class="line">        <span class="comment">// 取出所有顶点的邻接表迭代器</span></span><br><span class="line">        adj = (Iterator&lt;Integer&gt;[]) <span class="keyword">new</span> Iterator[vertex];</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> v = <span class="number">0</span>; v &lt; vertex; v++)</span><br><span class="line">            adj[v] = graph.adj(v).iterator();</span><br><span class="line"></span><br><span class="line">        dfs(originPoint);</span><br><span class="line">    &#125;</span><br><span class="line">	</span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> originPoint)</span> </span>&#123;</span><br><span class="line">        Stack&lt;Integer&gt; stack = <span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">		<span class="comment">// 标记起点并放入栈</span></span><br><span class="line">        marked[originPoint] = <span class="keyword">true</span>;</span><br><span class="line">        stack.push(originPoint);</span><br><span class="line">		</span><br><span class="line">        <span class="keyword">while</span> (!stack.isEmpty()) &#123;</span><br><span class="line">            Integer v = stack.peek();</span><br><span class="line">			<span class="comment">// 遍历栈顶顶点的邻接点</span></span><br><span class="line">            <span class="keyword">if</span> (adj[v].hasNext()) &#123;</span><br><span class="line">                <span class="keyword">int</span> w = adj[v].next();</span><br><span class="line">				<span class="comment">// 如果未被访问,进行标记并放入栈中</span></span><br><span class="line">                <span class="keyword">if</span> (!marked[w]) &#123;</span><br><span class="line">                    marked[w] = <span class="keyword">true</span>;</span><br><span class="line">                    stack.push(w);</span><br><span class="line">                &#125;</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">				<span class="comment">// 当栈顶顶点的所有邻接点已经遍历完时,弹出栈</span></span><br><span class="line">                stack.pop();</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="寻找路径"><a href="#寻找路径" class="headerlink" title="寻找路径"></a>寻找路径</h3><hr>
<p>在<code>图</code>的应用中,找出<code>v-w</code>的可达路径也是常见的问题之一.</p>
<p><img src="http://algs4.cs.princeton.edu/41graph/images/paths-api.png" alt="单点路径API"></p>
<p>我们基于<code>深度优先搜索</code>实现寻找路径,并添加一个<code>edgeTo[]</code>整形数组来记录路径.例如,在由边<code>v-w</code>第一次访问任意<code>w</code>时,将<code>edgeTo[w]</code>设为<code>v</code>来记录这条路径(<code>v-w</code>是从起点到<code>w</code>的路径上最后一条已知的边).这样搜索到的路径就是一颗以起点为根的树,<code>edgeTo[]</code>是一颗由父链接表示的树.</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">DepthFirstPaths</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">final</span> Graph graph;</span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">final</span> <span class="keyword">boolean</span>[] marked; </span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">final</span> <span class="keyword">int</span>[] edgeTo; <span class="comment">// 用于记录路径</span></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">final</span> <span class="keyword">int</span> originPoint;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">DepthFirstPaths</span><span class="params">(Graph graph, <span class="keyword">int</span> originPoint)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> vertex = graph.vertex();</span><br><span class="line">        <span class="keyword">this</span>.graph = graph;</span><br><span class="line">        <span class="keyword">this</span>.originPoint = originPoint;</span><br><span class="line">        <span class="keyword">this</span>.marked = <span class="keyword">new</span> <span class="keyword">boolean</span>[vertex];</span><br><span class="line">        <span class="keyword">this</span>.edgeTo = <span class="keyword">new</span> <span class="keyword">int</span>[vertex];</span><br><span class="line">        validateVertex(originPoint);</span><br><span class="line">        dfs(originPoint);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">hasPathTo</span><span class="params">(<span class="keyword">int</span> vertex)</span> </span>&#123;</span><br><span class="line">        validateVertex(vertex);</span><br><span class="line">        <span class="keyword">return</span> marked[vertex];</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> Iterable&lt;Integer&gt; <span class="title">pathTo</span><span class="params">(<span class="keyword">int</span> vertex)</span> </span>&#123;</span><br><span class="line">        validateVertex(vertex);</span><br><span class="line"></span><br><span class="line">        Stack&lt;Integer&gt; stack = <span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">		<span class="comment">// 从指定顶点处向上遍历路径(直到起点)</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> x = vertex; x != originPoint; x = edgeTo[x])</span><br><span class="line">            stack.push(x);</span><br><span class="line">        stack.push(originPoint);</span><br><span class="line">        <span class="keyword">return</span> stack;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> vertex)</span> </span>&#123;</span><br><span class="line">        marked[vertex] = <span class="keyword">true</span>;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> adj : graph.adj(vertex)) &#123;</span><br><span class="line">            <span class="keyword">if</span> (!marked[adj]) &#123;</span><br><span class="line">                marked[adj] = <span class="keyword">true</span>;</span><br><span class="line">				<span class="comment">// edgeTo[w] = v,记录了父链接</span></span><br><span class="line">                edgeTo[adj] = vertex;</span><br><span class="line">                dfs(adj);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">	</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="广度优先搜索"><a href="#广度优先搜索" class="headerlink" title="广度优先搜索"></a>广度优先搜索</h3><hr>
<p>对于寻找一条最短路径,<code>深度优先搜索</code>没有什么作为,因为它遍历整个图的顺序和找出最短路径的目标没有任何关系.这种问题就需要用到<code>广度优先搜索</code>.</p>
<p><code>广度优先搜索</code>是沿着宽度来进行搜索的.例如,要找到<code>s</code>到<code>v</code>的最短路径,<strong>从<code>s</code>开始,在所有由一条边就可以到达的<code>顶点</code>中寻找<code>v</code>,如果找不到就继续在与<code>s</code>距离两条边的所有顶点中寻找<code>v</code>,以此类推</strong>.</p>
<p>如果说<code>深度优先搜索</code>是一个人在走迷宫,那么<code>广度优先搜索</code>就是一群人一起朝着各个方向去走迷宫.</p>
<p>在<code>广度优先搜索</code>中,我们使用一个<code>队列</code>来保存所有已被标记过但<code>邻接表</code>还未被检查过的<code>顶点</code>.先将<code>起点</code>放入<code>队列</code>,然后重复以下步骤直到<code>队列</code>为空:</p>
<ul>
<li>取出<code>队列</code>中的下一个<code>顶点</code>并标记.</li>
</ul>
<ul>
<li>将它相邻的所有未被标记过的<code>顶点</code>加入队列.</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">BreadthFirstPaths</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> INFINITY = Integer.MAX_VALUE;</span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">final</span> Graph graph;</span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">final</span> <span class="keyword">boolean</span>[] marked; </span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">final</span> <span class="keyword">int</span>[] edgeTo;      </span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">final</span> <span class="keyword">int</span>[] distTo;      <span class="comment">// 记录路径中经过的顶点数,起点为0,需要全部初始化为无穷大</span></span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">BreadthFirstPaths</span><span class="params">(Graph graph, <span class="keyword">int</span> originPoint)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">this</span>.graph = graph;</span><br><span class="line">        <span class="keyword">int</span> vertex = graph.vertex();</span><br><span class="line">        marked = <span class="keyword">new</span> <span class="keyword">boolean</span>[vertex];</span><br><span class="line">        edgeTo = <span class="keyword">new</span> <span class="keyword">int</span>[vertex];</span><br><span class="line">        distTo = <span class="keyword">new</span> <span class="keyword">int</span>[vertex];</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; vertex; i++)</span><br><span class="line">            distTo[i] = INFINITY;</span><br><span class="line">        validateVertex(originPoint);</span><br><span class="line">        bfs(originPoint);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 以一组顶点为起点</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">BreadthFirstPaths</span><span class="params">(Graph graph, Iterable&lt;Integer&gt; sources)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">this</span>.graph = graph;</span><br><span class="line">        <span class="keyword">int</span> vertex = graph.vertex();</span><br><span class="line">        <span class="keyword">this</span>.marked = <span class="keyword">new</span> <span class="keyword">boolean</span>[vertex];</span><br><span class="line">        <span class="keyword">this</span>.edgeTo = <span class="keyword">new</span> <span class="keyword">int</span>[vertex];</span><br><span class="line">        <span class="keyword">this</span>.distTo = <span class="keyword">new</span> <span class="keyword">int</span>[vertex];</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; vertex; i++)</span><br><span class="line">            distTo[i] = INFINITY;</span><br><span class="line">        validateVertices(sources);</span><br><span class="line">        bfs(sources);</span><br><span class="line">    &#125;</span><br><span class="line">  </span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">hasPathTo</span><span class="params">(<span class="keyword">int</span> vertex)</span> </span>&#123;</span><br><span class="line">        validateVertex(vertex);</span><br><span class="line">        <span class="keyword">return</span> marked[vertex];</span><br><span class="line">    &#125;</span><br><span class="line">   </span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">distTo</span><span class="params">(<span class="keyword">int</span> vertex)</span> </span>&#123;</span><br><span class="line">        validateVertex(vertex);</span><br><span class="line">        <span class="keyword">return</span> distTo[vertex];</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> Iterable&lt;Integer&gt; <span class="title">pathTo</span><span class="params">(<span class="keyword">int</span> vertex)</span> </span>&#123;</span><br><span class="line">        validateVertex(vertex);</span><br><span class="line"></span><br><span class="line">        Stack&lt;Integer&gt; path = <span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">        <span class="keyword">int</span> x;</span><br><span class="line">		<span class="comment">// 这里使用distTo[x] != 0来判断是否为起点</span></span><br><span class="line">        <span class="keyword">for</span> (x = vertex; distTo[x] != <span class="number">0</span>; x = edgeTo[x])</span><br><span class="line">            path.push(x);</span><br><span class="line">        path.push(x);</span><br><span class="line">        <span class="keyword">return</span> path;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">bfs</span><span class="params">(<span class="keyword">int</span> vertex)</span> </span>&#123;</span><br><span class="line">        Queue&lt;Integer&gt; queue = <span class="keyword">new</span> ArrayDeque&lt;&gt;();</span><br><span class="line">        marked[vertex] = <span class="keyword">true</span>;</span><br><span class="line">        distTo[vertex] = <span class="number">0</span>;</span><br><span class="line">        queue.add(vertex);</span><br><span class="line"></span><br><span class="line">        searchAndMarkAdjacent(queue);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">bfs</span><span class="params">(Iterable&lt;Integer&gt; sources)</span> </span>&#123;</span><br><span class="line">        Queue&lt;Integer&gt; queue = <span class="keyword">new</span> ArrayDeque&lt;&gt;();</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> v : sources) &#123;</span><br><span class="line">            marked[v] = <span class="keyword">true</span>;</span><br><span class="line">            distTo[v] = <span class="number">0</span>;</span><br><span class="line">            queue.add(v);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        searchAndMarkAdjacent(queue);</span><br><span class="line">    &#125;</span><br><span class="line">	</span><br><span class="line">	<span class="comment">// 广度优先搜索</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">searchAndMarkAdjacent</span><span class="params">(Queue&lt;Integer&gt; queue)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">while</span> (!queue.isEmpty()) &#123;</span><br><span class="line">            Integer v = queue.remove();</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> adj : graph.adj(v)) &#123;</span><br><span class="line">				<span class="comment">// 将未标记过的邻接点加入队列并进行标记等操作</span></span><br><span class="line">                <span class="keyword">if</span> (!marked[adj]) &#123;</span><br><span class="line">                    marked[adj] = <span class="keyword">true</span>;</span><br><span class="line">                    edgeTo[adj] = v;</span><br><span class="line">                    distTo[adj] = distTo[v] + <span class="number">1</span>;</span><br><span class="line">                    queue.add(adj);</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">validateVertex</span><span class="params">(<span class="keyword">int</span> vertex)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> length = marked.length;</span><br><span class="line">        <span class="keyword">if</span> (vertex &lt; <span class="number">0</span> || vertex &gt;= length)</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;Vertex &quot;</span> + vertex + <span class="string">&quot; is not between 0 and &quot;</span> + (length - <span class="number">1</span>));</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">validateVertices</span><span class="params">(Iterable&lt;Integer&gt; vertices)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (vertices == <span class="keyword">null</span>)</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;Vertices is null.&quot;</span>);</span><br><span class="line"></span><br><span class="line">        <span class="keyword">int</span> length = marked.length;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> v : vertices) &#123;</span><br><span class="line">            <span class="keyword">if</span> (v &lt; <span class="number">0</span> || v &gt;= length)</span><br><span class="line">                <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;Vertex &quot;</span> + v + <span class="string">&quot; is not between 0 and &quot;</span> + (length - <span class="number">1</span>));</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>不管是<code>深度优先搜索</code>还是<code>广度优先搜索</code>,它们都是先将<code>起点</code>存入一个<code>数据结构</code>中,然后重复以下步骤直到<code>数据结构</code>被清空: </p>
<ul>
<li>取其中的下一个<code>顶点</code>并标记它.</li>
</ul>
<ul>
<li>将它的所有<code>相邻</code>而又未被标记的<code>顶点</code>放入<code>数据结构</code>中.</li>
</ul>
<p>这两种<code>算法</code>的<strong>不同之处仅在于从<code>数据结构</code>中获取下一个<code>顶点</code>的规则(对于<code>广度优先搜索</code>来说是最早加入的<code>顶点</code>,对于<code>深度优先搜索</code>来说是最晚加入的<code>顶点</code>)</strong>.</p>
<p><code>深度优先搜索</code>的方式是不断寻找离<code>起点</code>更远的<code>顶点</code>,直到碰见死胡同时才返回近处<code>顶点</code>.</p>
<p><code>广度优先搜索</code>的方式是先覆盖<code>起点</code>附近的<code>顶点</code>,只有当<code>邻接</code>的所有<code>顶点</code>都被访问过之后才继续前进.</p>
<p><code>深度优先搜素</code>的路径通常长且曲折,<code>广度优先搜索</code>的路径则短而直接.但不管是使用哪种<code>算法</code>,所有与<code>起点</code>连通的<code>顶点</code>和<code>边</code>都会被访问到.</p>
<h3 id="连通分量"><a href="#连通分量" class="headerlink" title="连通分量"></a>连通分量</h3><hr>
<p><code>深度优先搜索</code>的一个重要应用就是寻找出一幅<code>图</code>中的所有连通分量.</p>
<p><img src="http://algs4.cs.princeton.edu/41graph/images/cc-api.png" alt="连通分量API"></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">ConnectedComponent</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">final</span> Graph graph;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">final</span> <span class="keyword">boolean</span>[] marked;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 顶点与它们所属的连通分量进行关联的数组</span></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">final</span> <span class="keyword">int</span>[] id;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 记录每个连通分量中有多少顶点的数组</span></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">final</span> <span class="keyword">int</span>[] size;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 连通分量数</span></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span> count;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">ConnectedComponent</span><span class="params">(Graph graph)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">this</span>.graph = graph;</span><br><span class="line">        <span class="keyword">int</span> vertex = graph.vertex();</span><br><span class="line">        <span class="keyword">this</span>.marked = <span class="keyword">new</span> <span class="keyword">boolean</span>[vertex];</span><br><span class="line">        <span class="keyword">this</span>.id = <span class="keyword">new</span> <span class="keyword">int</span>[vertex];</span><br><span class="line">        <span class="keyword">this</span>.size = <span class="keyword">new</span> <span class="keyword">int</span>[vertex];</span><br><span class="line"></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> v = <span class="number">0</span>; v &lt; vertex; v++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (!marked[v]) &#123;</span><br><span class="line">                dfs(v);</span><br><span class="line">                count++; <span class="comment">// 一张连通图遍历完毕后,连通分量数 + 1</span></span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">id</span><span class="params">(<span class="keyword">int</span> vertex)</span> </span>&#123;</span><br><span class="line">        validateVertex(vertex);</span><br><span class="line">        <span class="keyword">return</span> id[vertex];</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">size</span><span class="params">(<span class="keyword">int</span> vertex)</span> </span>&#123;</span><br><span class="line">        validateVertex(vertex);</span><br><span class="line">        <span class="keyword">return</span> size[id[vertex]];</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">count</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> count;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 两个顶点是否处于一个连通分量中</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">connected</span><span class="params">(<span class="keyword">int</span> v, <span class="keyword">int</span> w)</span> </span>&#123;</span><br><span class="line">        validateVertex(v);</span><br><span class="line">        validateVertex(w);</span><br><span class="line">        <span class="keyword">return</span> id[v] == id[w];</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> vertex)</span> </span>&#123;</span><br><span class="line">        marked[vertex] = <span class="keyword">true</span>;</span><br><span class="line">        id[vertex] = count;</span><br><span class="line">        size[count]++;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> adj : graph.adj(vertex)) &#123;</span><br><span class="line">            <span class="keyword">if</span> (!marked[adj])</span><br><span class="line">                dfs(adj);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">	</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="检测环与双色问题"><a href="#检测环与双色问题" class="headerlink" title="检测环与双色问题"></a>检测环与双色问题</h3><hr>
<p><code>深度优先搜索</code>的应用远不于此,它还可以用来检测是否有环以及双色问题.</p>
<h4 id="检测环"><a href="#检测环" class="headerlink" title="检测环"></a>检测环</h4><hr>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">Cyclic</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">final</span> Graph graph;</span><br><span class="line">	</span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">boolean</span>[] marked</span><br><span class="line">	;</span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span>[] edgeTo;</span><br><span class="line">	<span class="comment">// 如果存在环则返回这条环路径</span></span><br><span class="line">    <span class="keyword">private</span> Stack&lt;Integer&gt; cyclic;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">Cyclic</span><span class="params">(Graph graph)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">this</span>.graph = graph;</span><br><span class="line">		<span class="comment">// 先检测是否有自环</span></span><br><span class="line">        <span class="keyword">if</span> (hasSelfLoop()) <span class="keyword">return</span>;</span><br><span class="line">		<span class="comment">// 再检测是否有平行边</span></span><br><span class="line">        <span class="keyword">if</span> (hasParallelEdges()) <span class="keyword">return</span>;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">int</span> vertex = graph.vertex();</span><br><span class="line">        <span class="keyword">this</span>.marked = <span class="keyword">new</span> <span class="keyword">boolean</span>[vertex];</span><br><span class="line">        <span class="keyword">this</span>.edgeTo = <span class="keyword">new</span> <span class="keyword">int</span>[vertex];</span><br><span class="line"></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> v = <span class="number">0</span>; v &lt; vertex; v++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (!marked[v])</span><br><span class="line">                dfs(v, -<span class="number">1</span>);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">hasCyclic</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> cyclic != <span class="keyword">null</span>;</span><br><span class="line">    &#125;</span><br><span class="line">	</span><br><span class="line">    <span class="function"><span class="keyword">public</span> Iterable&lt;Integer&gt; <span class="title">cyclic</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> cyclic;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">boolean</span> <span class="title">hasSelfLoop</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> v = <span class="number">0</span>; v &lt; graph.vertex(); v++) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> w : graph.adj(v)) &#123;</span><br><span class="line">				<span class="comment">// 如果v与w是同一个顶点,则代表有自环</span></span><br><span class="line">                <span class="keyword">if</span> (v == w) &#123;</span><br><span class="line">                    cyclic = <span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">                    cyclic.push(v);</span><br><span class="line">                    cyclic.push(v);</span><br><span class="line">                    <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">boolean</span> <span class="title">hasParallelEdges</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> vertex = graph.vertex();</span><br><span class="line">        <span class="keyword">boolean</span>[] marked = <span class="keyword">new</span> <span class="keyword">boolean</span>[vertex];</span><br><span class="line">		</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> v = <span class="number">0</span>; v &lt; vertex; v++) &#123;</span><br><span class="line">            <span class="comment">// check for parallel edges incident to v</span></span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> w : graph.adj(v)) &#123;</span><br><span class="line">                <span class="keyword">if</span> (marked[w]) &#123;</span><br><span class="line">                    cyclic = <span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">                    cyclic.push(v);</span><br><span class="line">                    cyclic.push(w);</span><br><span class="line">                    cyclic.push(v);</span><br><span class="line">                    <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">                &#125;</span><br><span class="line">                marked[w] = <span class="keyword">true</span>;</span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line">            <span class="comment">// reset so marked[v] = false for all v</span></span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> w : graph.adj(v))</span><br><span class="line">                marked[w] = <span class="keyword">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> v, <span class="keyword">int</span> u)</span> </span>&#123;</span><br><span class="line">        marked[v] = <span class="keyword">true</span>;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> w : graph.adj(v)) &#123;</span><br><span class="line">            <span class="keyword">if</span> (cyclic != <span class="keyword">null</span>) <span class="keyword">return</span>;</span><br><span class="line">            <span class="keyword">if</span> (!marked[w]) &#123;</span><br><span class="line">                edgeTo[w] = v;</span><br><span class="line">                dfs(w, v);</span><br><span class="line">            &#125; <span class="keyword">else</span> <span class="keyword">if</span> (w != u) &#123;</span><br><span class="line">                <span class="comment">// check for cycle (but disregard reverse of edge leading to v)</span></span><br><span class="line">                cyclic = <span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">                <span class="keyword">for</span> (<span class="keyword">int</span> x = v; x != w; x = edgeTo[x])</span><br><span class="line">                    cyclic.push(x);</span><br><span class="line">                cyclic.push(w);</span><br><span class="line">                cyclic.push(v);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h4 id="检测双色"><a href="#检测双色" class="headerlink" title="检测双色"></a>检测双色</h4><hr>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">TwoColor</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">final</span> Graph graph;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">final</span> <span class="keyword">boolean</span>[] marked;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">final</span> <span class="keyword">boolean</span>[] color;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">boolean</span> isTwoColorable = <span class="keyword">true</span>;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">TwoColor</span><span class="params">(Graph graph)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">this</span>.graph = graph;</span><br><span class="line">        <span class="keyword">int</span> vertex = graph.vertex();</span><br><span class="line"></span><br><span class="line">        <span class="keyword">this</span>.marked = <span class="keyword">new</span> <span class="keyword">boolean</span>[vertex];</span><br><span class="line">        <span class="keyword">this</span>.color = <span class="keyword">new</span> <span class="keyword">boolean</span>[vertex];</span><br><span class="line"></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> v = <span class="number">0</span>; v &lt; vertex; v++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (!marked[v])</span><br><span class="line">                dfs(v);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isBipartite</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> isTwoColorable;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> v)</span> </span>&#123;</span><br><span class="line">        marked[v] = <span class="keyword">true</span>;</span><br><span class="line">		</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> w : graph.adj(v)) &#123;</span><br><span class="line">            <span class="keyword">if</span> (!marked[w]) &#123;</span><br><span class="line">				<span class="comment">// 将未被访问过的邻接点w设为v的反色</span></span><br><span class="line">                color[w] = !color[v];</span><br><span class="line">                dfs(w);</span><br><span class="line">            &#125; <span class="keyword">else</span> <span class="keyword">if</span> (color[w] == color[v]) &#123;</span><br><span class="line">				<span class="comment">// 如果w已被访问且颜色与v相同,则代表这不是一张双色图</span></span><br><span class="line">                isTwoColorable = <span class="keyword">false</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="符号图"><a href="#符号图" class="headerlink" title="符号图"></a>符号图</h3><hr>
<p>在很多应用中,是使用字符串而非整数来表示<code>顶点</code>的,为了适应这种需求,需要拥有以下性质的输入格式: </p>
<ul>
<li>顶点名是字符串.</li>
</ul>
<ul>
<li>用指定的分隔符来隔开顶点名</li>
</ul>
<ul>
<li>每一行都表示一组边的集合,每一条边都连接着这一行的第一个名称表示的顶点和其他名称所表示的顶点.</li>
</ul>
<ul>
<li>顶点集<code>V</code>与边集<code>E</code>都是隐式定义的.</li>
</ul>
<p><img src="http://algs4.cs.princeton.edu/41graph/images/routes.png" alt="符号图的输入格式"></p>
<p>要实现<code>符号图</code>还需要借助以下数据结构: </p>
<ul>
<li>一个<code>符号表</code>,我这里使用的是<code>TreeMap</code>即<code>红黑树</code>,它的<code>Key</code>为<code>String</code>(顶点名),<code>Value</code>为<code>Integer</code>(顶点索引).</li>
</ul>
<ul>
<li>一个<code>字符串数组</code>,它用来与<code>符号表</code>作<code>反向索引</code>,保存每个<code>顶点</code>索引所对应的<code>顶点名</code>.</li>
</ul>
<ul>
<li>一个<code>Graph</code>对象,我们使用索引来生成这张<code>图</code>对象.</li>
</ul>
<p><img src="http://algs4.cs.princeton.edu/41graph/images/symbol-graph-api.png" alt="符号图的API"></p>
<p><img src="http://algs4.cs.princeton.edu/41graph/images/symbol-graph.png" alt="需要用到的数据结构"></p>
<h4 id="代码实现"><a href="#代码实现" class="headerlink" title="代码实现"></a>代码实现</h4><hr>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">SymbolGraph</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> TreeMap&lt;String, Integer&gt; symbolTable; <span class="comment">// string -&gt; index</span></span><br><span class="line">    <span class="keyword">private</span> String[] keys; <span class="comment">// index -&gt; string</span></span><br><span class="line">    <span class="keyword">private</span> Graph graph;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">SymbolGraph</span><span class="params">(String filename, String delimiter)</span> </span>&#123;</span><br><span class="line">        symbolTable = <span class="keyword">new</span> TreeMap&lt;&gt;();</span><br><span class="line"></span><br><span class="line">        <span class="comment">// 第一次读取文件</span></span><br><span class="line">        String filePath = <span class="string">&quot;/graph_file/C4_1_UndirectedGraphs/&quot;</span> + filename;</span><br><span class="line">        InputStream inputStream</span><br><span class="line">                = SymbolGraph.class.getResourceAsStream(filePath);</span><br><span class="line">        Scanner scanner = <span class="keyword">new</span> Scanner(inputStream, <span class="string">&quot;UTF-8&quot;</span>);</span><br><span class="line"></span><br><span class="line">        <span class="comment">// 初始化符号表</span></span><br><span class="line">        <span class="keyword">while</span> (scanner.hasNextLine()) &#123;</span><br><span class="line">            String[] s = scanner.nextLine().split(delimiter);</span><br><span class="line">            <span class="keyword">for</span> (String key : s) &#123;</span><br><span class="line">                <span class="keyword">if</span> (!symbolTable.containsKey(key))</span><br><span class="line">                    symbolTable.put(key, symbolTable.size());</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        System.out.printf(<span class="string">&quot;Done reading %s!\n&quot;</span>, filename);</span><br><span class="line"></span><br><span class="line">        <span class="comment">// 初始化反向索引</span></span><br><span class="line">        keys = <span class="keyword">new</span> String[symbolTable.size()];</span><br><span class="line">        <span class="keyword">for</span> (String name : symbolTable.keySet())</span><br><span class="line">            keys[symbolTable.get(name)] = name;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// 第二次读取文件,并生成图</span></span><br><span class="line">        graph = <span class="keyword">new</span> UndirectedGraph(symbolTable.size());</span><br><span class="line">        Scanner create_graph_scanner = <span class="keyword">new</span> Scanner(SymbolGraph.class.getResourceAsStream(filePath));</span><br><span class="line">        <span class="keyword">while</span> (create_graph_scanner.hasNextLine()) &#123;</span><br><span class="line">            String[] s = create_graph_scanner.nextLine().split(delimiter);</span><br><span class="line">			<span class="comment">// 将第一行的第一个顶点与其他顶点相连</span></span><br><span class="line">            <span class="keyword">int</span> v = symbolTable.get(s[<span class="number">0</span>]);</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; s.length; i++) &#123;</span><br><span class="line">                <span class="keyword">int</span> w = symbolTable.get(s[i]);</span><br><span class="line">                graph.addEdge(v, w);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">contains</span><span class="params">(String s)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> symbolTable.containsKey(s);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">indexOf</span><span class="params">(String s)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> symbolTable.get(s);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> String <span class="title">nameOf</span><span class="params">(<span class="keyword">int</span> v)</span> </span>&#123;</span><br><span class="line">        validateVertex(v);</span><br><span class="line">        <span class="keyword">return</span> keys[v];</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> Graph <span class="title">graph</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> graph;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="参考资料"><a href="#参考资料" class="headerlink" title="参考资料"></a>参考资料</h3><hr>
<ul>
<li><a target="_blank" rel="noopener" href="https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)">Graph (discrete mathematics) - Wikipedia</a></li>
</ul>
<ul>
<li><a target="_blank" rel="noopener" href="https://en.wikipedia.org/wiki/Bipartite_graph">Bipartite graph - Wikipedia</a></li>
</ul>
<ul>
<li><a target="_blank" rel="noopener" href="http://algs4.cs.princeton.edu/41graph/">Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne</a></li>
</ul>
<blockquote>
<p>本文作者为<a target="_blank" rel="noopener" href="https://github.com/SylvanasSun">SylvanasSun(sylvanassun_xtz@163.com)</a>,转载请务必指明原文链接.</p>
</blockquote>
<h3 id="图的那点事儿"><a href="#图的那点事儿" class="headerlink" title="图的那点事儿"></a>图的那点事儿</h3><hr>
<ul>
<li><a target="_blank" rel="noopener" href="https://sylvanassun.github.io/2017/07/18/2017-07-18-Graph_UndirectedGraph/">图的那点事儿(1)-无向图</a></li>
</ul>
<ul>
<li><a target="_blank" rel="noopener" href="https://sylvanassun.github.io/2017/07/23/2017-07-23-Graph_DirectedGraphs/">图的那点事儿(2)-有向图</a></li>
</ul>
<ul>
<li><a target="_blank" rel="noopener" href="https://sylvanassun.github.io/2017/07/25/2017-07-25-Graph_WeightedUndirectedGraph/">图的那点事儿(3)-加权无向图</a></li>
</ul>
<ul>
<li><a target="_blank" rel="noopener" href="https://sylvanassun.github.io/2017/07/27/2017-07-27-Graph_WeightedDigraph">图的那点事儿(4)-加权有向图</a></li>
</ul>

    </div>

    
    
    

    <footer class="post-footer">
          <div class="post-tags">
              <a href="/yuwanzi.io/tags/2017/" rel="tag"># 2017</a>
              <a href="/yuwanzi.io/tags/Algorithms/" rel="tag"># Algorithms</a>
              <a href="/yuwanzi.io/tags/Graph/" rel="tag"># Graph</a>
          </div>

        

          <div class="post-nav">
            <div class="post-nav-item">
                <a href="/yuwanzi.io/2017/06/27/2017-06-27-DynamicProgramming/" rel="prev" title="什么是动态规划?">
                  <i class="fa fa-chevron-left"></i> 什么是动态规划?
                </a>
            </div>
            <div class="post-nav-item">
                <a href="/yuwanzi.io/2017/07/19/2017-07-19-FaceMash/" rel="next" title="电影<<社交网络>>中的"FaceMash"算法">
                  电影<<社交网络>>中的"FaceMash"算法 <i class="fa fa-chevron-right"></i>
                </a>
            </div>
          </div>
    </footer>
  </article>
</div>







<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      const activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      const commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>
</div>
  </main>

  <footer class="footer">
    <div class="footer-inner">


<div class="copyright">
  &copy; 
  <span itemprop="copyrightYear">2021</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">玉丸子</span>
</div>
  <div class="powered-by">Erstellt mit  <a href="https://hexo.io/" class="theme-link" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.js.org/muse/" class="theme-link" rel="noopener" target="_blank">NexT.Muse</a>
  </div>

    </div>
  </footer>

  
  <script src="//cdn.jsdelivr.net/npm/animejs@3.2.1/lib/anime.min.js"></script>
<script src="/yuwanzi.io/js/utils.js"></script><script src="/yuwanzi.io/js/motion.js"></script><script src="/yuwanzi.io/js/schemes/muse.js"></script><script src="/yuwanzi.io/js/next-boot.js"></script>

  






  





</body>
</html>
